#!/usr/bin/env python
# -*- encoding: utf-8 -*-
'''
@File    :   排序.py
@Time    :   2022/01/12 16:15:08
@Author  :   glx 
@Version :   1.0
@Contact :   18095542g@connect.polyu.hk
@Desc    :   None
'''

# here put the import lib


from pickle import GLOBAL


def Bubble_sort(x, reverse = False):
    """ 冒泡算法 """
    for j in range(len(x)):
        changed = False
        for i in range(len(x)-1):
            
            if x[i] > x[i+1]:
                x[i], x[i+1] = x[i+1], x[i]
                changed = True
        if not changed:
            break
    return x[::-1] if reverse else x


def Insert_sort(x, reverse = False): 
    """ 插入排序 """
    for i in range(1, len(x)): 
        key = x[i] 
        j = i-1 # 待插入元素的前一个元素
        while j >=0 and key < x[j] : # 找位置
                x[j+1] = x[j] # 数据往后移动
                j -= 1
        x[j+1] = key # 插入
    return x[::-1] if reverse else x


def Select_sort(x, reverse = False):
    """ 选择排序 """
    for i in range(len(x)):
        min_idx = i # 最小元素的索引
        for j in range(i+1, len(x)): # 找最小元素
            if x[j] < x[min_idx]:
                min_idx = j 
        x[i], x[min_idx] = x[min_idx], x[i] # 把最小的交换到i位置
    return x[::-1] if reverse else x

## 归并排序
def Merge_sort(x, reverse = False):
    """ 归并排序 """
    if len(x) <= 1:
        return x
    mid = len(x)//2
    left = Merge_sort(x[:mid])
    right = Merge_sort(x[mid:])
    return Merge(left, right, reverse)

def Merge(left, right,reverse = False):
    """ 合并两个有序数组 """
    res = []
    l, r = 0, 0
    while l<len(left) and r<len(right):
        if left[l] < right[r]:
            res.append(left[l])
            l+=1
        else:
            res.append(right[r])
            r+=1
    if l == len(left):
        res += right[r:]
    else:
        res += left[l:]
    return res[::-1] if reverse else res


def Quick_sort(x, reverse = False):
    """ 快速排序 """
    if len(x) <= 1:
        return x
    key = x[0]
    left = [i for i in x[1:] if i <= key]
    right = [i for i in x[1:] if i > key]
    return Quick_sort(left, reverse) + [key] + Quick_sort(right, reverse) if reverse else Quick_sort(left, reverse) + [key] + Quick_sort(right, reverse)[::-1]


if __name__ == "__main__":
    x = [1,2,3,4,5,6,7,8,9][::-1]
    # print("冒泡排序算法:", Bubble_sort(x))
    # print("插入排序算法:", Insert_sort(x))
    # print("选择排序算法:", Select_sort(x))
    # print("归并排序算法:", Merge_sort(x))
    print("快速排序算法:", Quick_sort(x))

